package test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * Created by Caesar on 2016/4/14.
 * 判断一个字符串的最大回文子串，并且可以删除其中的元素
 * 例如：字符串cabebaf 最大回文子串为abeba，cf被删除
 */
public class Palindrome {
    public int palindrome(String str) {
        if (str.length() == 2) {
            char[] stra = str.toCharArray();
            if (stra[0] == stra[1])
                return 2;
            else
                return 0;
        }
        if (str.length() == 1)
            return 1;
        Map<Character, ArrayList<Integer>> temp = new HashMap<Character, ArrayList<Integer>>();
        char[] temp2 = str.toCharArray();
        for (int i = 0; i < temp2.length; i++) {
            if (temp.containsKey(temp2[i]))
                temp.get(temp2[i]).add(i);
            else {
                ArrayList<Integer> arr = new ArrayList<Integer>();
                arr.add(i);
                temp.put(temp2[i], arr);
            }
        }

        int max = 0;
        ArrayList<Integer> arrtmp = temp.get(temp2[0]);
        int first = arrtmp.get(0);
        int last = arrtmp.get(arrtmp.size() - 1);
        if (first != last) {
            int res = 2 + palindrome(str.substring(first, last));
            if (max < res)
                max = res;
        } else {
            int res = 1 + palindrome(str.replace(temp2[first] + "", ""));
            if (max < res)
                max = res;
        }
        arrtmp = temp.get(temp2[temp2.length - 1]);
        first = arrtmp.get(0);
        last = arrtmp.get(arrtmp.size() - 1);
        if (first != last) {
            int res = 2 + palindrome(str.substring(first, last));
            if (max < res)
                max = res;
        } else {
            int res = 1 + palindrome(str.replace(temp2[first] + "", ""));
            if (max < res)
                max = res;
        }
        int res = palindrome(str.substring(1, str.length() - 1));
        if (max < res)
            max = res;
        return max;
    }

    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);
        String str = scanner.next();*/
        Palindrome pal = new Palindrome();
        System.out.println(pal.palindrome("askjdhfksa"));
        /*String str = "askjdhfksa";
        System.out.println(str.substring(1, str.length() - 1));*/

    }
}
